package first

/*
	定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

	 

	示例:

	MinStack minStack = new MinStack();
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	minStack.min();   --> 返回 -3.
	minStack.pop();
	minStack.top();      --> 返回 0.
	minStack.min();   --> 返回 -2.
	 

	提示：

	各函数的调用总次数不超过 20000 次

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
type MinStack struct {
	stack       []int
	assistStack []int
	/*
		维护一个辅助栈assistStack, 该栈负责维护最小值、在push的时候作如下处理：
		1. 栈为空、元素压栈
		2. 当前要入栈的元素小于等于assistStack的栈顶元素、元素压栈
		通过以上方式保证assistStack的栈顶元素始终是当前stack中的最小元素
		出栈时则做如下判断
		1. 当前出栈(stack)的元素与assistStack的栈顶元素相等、assistStack也出栈
		通过以上方式保证出栈时、stack与assistStack中最小元素的一致性
	*/
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{
		stack:       make([]int, 0),
		assistStack: make([]int, 0),
	}
}

func (this *MinStack) Push(x int) {
	this.stack = append(this.stack, x)
	if len(this.assistStack) == 0 || this.assistStack[len(this.assistStack)-1] >= x {
		this.assistStack = append(this.assistStack, x)
	}

}

func (this *MinStack) Pop() {
	topValue := this.stack[len(this.stack)-1]
	this.stack = this.stack[0 : len(this.stack)-1]
	if topValue == this.assistStack[len(this.assistStack)-1] {
		this.assistStack = this.assistStack[:len(this.assistStack)-1]
	}
}

func (this *MinStack) Top() int {
	return this.stack[len(this.stack)-1]
}

func (this *MinStack) Min() int {
	if len(this.assistStack) == 0 {
		return 0
	}
	return this.assistStack[len(this.assistStack)-1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Min();
 */
